#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int trap(vector<int> &height)
    {
        vector<int> left(height.size(), 0);
        vector<int> right(height.size(), 0);
        left[0] = height[0];
        for (int i = 1; i < height.size(); i++)
        {
            left[i] = max(left[i - 1], height[i]);
        }
        right[height.size() - 1] = height[height.size() - 1];
        for (int i = height.size() - 2; i >= 0; i--)
        {
            right[i] = max(right[i + 1], height[i]);
        }
        int total = 0;
        for (int i = 0; i < height.size(); i++)
        {
            total += min(left[i], right[i]) - height[i];
        }
        return total;
    }
};
int main()
{
    cout << "Code42" << endl;
    Solution s;
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    cout << s.trap(height) << endl;
    return 0;
}